package kmp;

import java.util.Arrays;

public class kmpTest {

    public static void main(String[] args) {
        System.out.println(strStr("ababababcabacacababaca", "ababaca"));
//        System.out.println("ababababcabacacababaca".indexOf("ababaca"));
        System.out.println(  Arrays.toString(lps("niconiconi".toCharArray())));

    }

    public static int strStr(String str1, String str2) {
        char[] origin = str1.toCharArray(); //原始
        char[] patten = str2.toCharArray(); //模式
        int[] lps = lps(patten);    //最长前后后缀数组
        //匹配成功 i++ j++
        //失败 j!=0 跳过 最长前后缀字符 继续匹配
        //j==0 则i++
        int i = 0;
        int j = 0;
        while (patten.length <= origin.length - i) {
            if (origin[i] == patten[j]) {
                i++;
                j++;
            } else if (j == 0) {
                i++;
            } else {
                j = lps[j - 1];
            }
            if (j == patten.length) {//找到解了
                return i - j;  //i的长度减去模式字符串的长度
            }
        }
        return -1;
    }

    static int[] lps(char[] patten) {
        int[] lps = new int[patten.length];
        int i = 1;
        int j = 0;
        while (i < patten.length) {
            if (patten[i] == patten[j]) {//找了相同字符
                lps[i] = j + 1;
                i++;
                j++;
            } else if (j == 0) {
                i++;
            } else {
                j = lps[j - 1];
            }
        }
        return lps;
    }
}
